package DynamicProgramming;//给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,5,11,5]
//输出：true
//解释：数组可以分割成 [1, 5, 5] 和 [11] 。 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,5]
//输出：false
//解释：数组不能分割成两个元素和相等的子集。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 200 
// 1 <= nums[i] <= 100 
// 
// Related Topics 数组 动态规划 👍 1010 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class canPartition {

    boolean flag = false;

    public boolean canPartition1(int[] nums) {

        /**
         * 回溯法 超时
         * */
        int len = nums.length;
        if(len<2){
            return false;
        }

        int sum = Arrays.stream(nums).sum();  //求和
        //只包含正整数,如果出现奇数，一半会出现小数，则不可能找到
        if(sum%2==1){
            return false;
        }
        backTrack(nums, sum/2, 0);
        return flag;


    }

    private void backTrack(int[] nums, double num, int start){
        if(num==0){
            flag = true;
        }
        //因为只有正整数，所以一旦 半数的值小于0则说明和超过了半数，则返回上层
        if(num<0){
            return ;
        }
        for (int i = start; i < nums.length; i++) {
            num -= nums[i];
            backTrack(nums,num, i+1);
            num += nums[i];
        }
    }

    public boolean canPartition(int[] nums) {
        /**
         * 题目要求只包含正整数
         * 动态规划
         * 此题 换种说法即数组中能否找出相加为总元素和一半的元素
         * 转化为01背包问题
         * 即数组中的元素值即 weight和value，背包总重为 sum/2，当背包负重为sum/2的最大价值也为sum/2即可以找到
         * */
        int len = nums.length;
        if(len<2){
            return false;
        }
        int sum = Arrays.stream(nums).sum();  //求和
        //只包含正整数,如果出现奇数，一半会出现小数，则不可能找到
        if(sum%2==1){
            return false;
        }
        int target = sum/2;  //总和的一半
        //动规数组，dp[i]表示总和为i的要求下，最大能存入的元素，当i==dp[i]时，说明可以找到
        int[] dp = new int[target+1];
        for (int i = 0; i < len; i++) {
            for (int j = target; j >= nums[i] ; j--) {
                dp[j] = Math.max(dp[j-nums[i]] + nums[i], dp[j]);
            }
        }

        //如果最终能找到i==dp[i]，则成功
        return dp[target] == target;

    }

    public boolean canPartition2(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        //一维01背包
        // int[] dp = new int[target + 1];
        // for(int i = 0; i < n; i++){
        //     for(int j = target; j >= nums[i]; j--){
        //         //物品 i 的重量是 nums[i]，其价值也是 nums[i]
        //         dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
        //     }
        // }
        // return dp[target] == target;

        //二维01背包,横坐标为物品，纵坐标为容量，该题物品的重量和价值相同
        int[][] dp = new int[n][target+1];
        //初始化，第一列容量为0时，最大价值为0；
        for(int i=0;i<n;i++){
            dp[i][0] = 0;
        }
        //第一行 放只第一个物品时的最大价值
        for(int i=0;i<target+1;i++){
            if(nums[0] < i){
                dp[0][i] = nums[0];
            }
        }
        //先遍历物品，再遍历容量
        for(int i=1;i<n;i++){
            for(int j=1;j<target+1;j++){
                //当前容量能放下物品时，要比较，不能放下时，还取不放当前物品时的容量
                if (j >= nums[i]) {
                    //能放下时，比较不放当前容量时的最大价值 和 不放当前物品且刚好能放下当前物品时的价值和当前物品价值和 取最大的
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n-1][target] == target;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
